//
//  SString.cpp
//  DataStructure
//
//  Created by 劢克科技 on 2020/7/23.
//  Copyright © 2020 Shuleiming. All rights reserved.
//

#include "SString.hpp"

// 赋值操作
void StrAssign(SString &T, char *chars)
{
    int i = 0;
    for (; chars[i] != '\0'; i++) {
        T.ch[i + 1] = chars[i];
    }
    T.length = i;
}

// 求子串
// 1.判断pos+len-1是否超出S的边界
// 2.获取字符并赋值给子串，指针范围：pos ~ pos + len - 1
bool SubString(SString &Sub, SString S, int pos, int len)
{
    // 判断取值范围是否合法
    if (pos < 1 || pos + len - 1 > S.length) {
        return false;
    }
    // 将字串复制到Sub中
    for (int i = pos; i < pos + len; i++) {
        Sub.ch[i - pos +1] = S.ch[i];
    }
    Sub.length = len;
    return true;
}

// *比较字符串大小*
// 指针i从1开始向后扫描，直到超过S或T的长度
// 扫描过程中，如果S[i] != T[i]时，可比较大小
// 扫描完毕，还未发现不同的字符，则比较长度，长的字符串更大
int StrCompare(SString S, SString T)
{
    int i = 1, n = S.length, m = T.length;
    for (; i <= n && i <= m; i++) {
        if (S.ch[i] != T.ch[i])
            return S.ch[i] - T.ch[i];
    }
    return S.length - T.length; // 扫描的字符一样则比较长度
}

// **定位操作** 找到S中T子串的位置，如不存在则返回0
// 1.pos从1开始取S的子串sub
// 2.比较sub和T，若sub与T相同，返回当前pos；
// 3.找不到匹配的子串则返回0
int Index(SString S, SString T)
{
    int pos = 1, n = S.length, m = T.length;
    SString sub;
    while (pos + m - 1 <= n) {
        SubString(sub, S, pos, m); // 取子串比较
        if (StrCompare(sub, T) == 0)
            return pos;
        pos++;
    }
    return 0;
}

// **朴素定位操作**
// 1.令指针k=1
// 2.指针i=k指向S,j=1指向T
// 3.比较S.ch[i]和T.ch[j]，若相同，则i++,j++继续比较；若不同，k++并从2开始重复操作
// 4.判断比较结果返回位置
int BFIndex(SString S, SString T)
{
    int k = 1;
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length) {
        if (S.ch[i] == T.ch[j]) {
            i++;j++;
        } else {
            k++;
            i = k;
            j = 1;
        }
    }
    return j > T.length ? k : 0;
}

// *** KMP算法模式匹配 ***
int Index_KMP(SString S, SString T, int next[])
{
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length) {
        if (j==0 || S.ch[i] == T.ch[j]) {
            i++;j++;
        } else {
            j = next[j];
        }
    }
    return j > T.length ? i - T.length : 0;
}
